1. Field of the Invention
This invention relates to computer graphics systems and, more particularly, to an especially efficient process for clipping polygons.
2. History of the Prior Art
In computer graphic systems, it is necessary to represent both two and three dimensional pictures on a two dimensional screen. Often a portion of the actual picture to be represented falls outside the field of vision provided by the screen. This is especially true where the computer graphic system is one employing windows to define small areas of the screen within which individual programs or processes may be running.
In all such cases, it is necessary to select the desired portion of the picture which is to appear within the screen or the window of the screen. This process of selecting the desired portion and rejection the undesired portion has been termed "polygon clipping." It is essentially a process whereby a polygonal surface extending beyond the boundary of the selected area of the screen in which it is to appear is limited to the portion within the chosen area of the screen.
Although many clipping algorithms have been proposed and used, the Sutherland-Hodgman polygon clipping algorithm is the only simple and completely accurate algorithm for clipping polygons to a three dimensional volume.
This clipping algorithm is disclosed in U.S. Pat. No. 3,816,726, issued June 11, 1974. Basically, the algorithm treats both two and three dimensional images as a plurality of individual polygons. The polygons which may be clipped and then recomposed to represent the images in the scene. The clipping algorithm views the polygons as they would be seen within a truncated pyramid leading from the eye of the viewer. It clips each polygon to fit within the six planes which define that pyramid. These six planes are a top plane, a bottom plane, a left plane, a right plane, a near plane (which lies in the plane of the screen of the viewing device), and a far plane. The near and far planes are referred to in the above referenced patent as the hither and yon planes. Before beginning the clipping operation, a limited transformation is applied to the data provided for the image to be defined to place the clipping planes at any desired locations. The algorithm commences comparing the polygonal shape to the clipping surfaces using only the vertices defining the polygon.
For each polygon, the vertices are treated one at a time from a beginning vertex. In each comparison, the algorithm determines whether the newly-considered vertex lies within the visible area or outside of it. From this and the just-previously-considered vertex, it determines what values to output, what intersections to compute, and so on. It will be understood that there are only four possible ways in which a line joining two vertices of a polygon may relate to a particular clipping plane. The line may lie entirely within the visible area defined by that clipping plane, it may lie entirely out of the visible area defined by that plane, it may cross from the visible to the invisible area defined by the plane, or it may cross from the invisible to the visible area.
The algorithm takes the beginning vertex of the polygon and stores its value as a first vertex value so that the algorithm may determine when the polygon has closed upon itself. The algorithm then determines whether the beginning vertex is within the visible portion of the display. If the vertex is within the visible portion of the display, it is provided as an output to be displayed. As each vertex is considered, it is also saved and designated as vertex S the saved vertex. The algorithm then considers the second vertex. The first determination is whether the second vertex is on the same side of the clipping plane as the last vertex, saved as vertex S. If this new vertex is in the visible area and if the saved vertex S is in the visible area, the new vertex is also provided as an output and is stored as the new vertex S. If, on the other hand, the new vertex is outside the visible area with respect to the particular clipping plane, the algorithm computes the point of intersection I with the clipping plane of the line between the new vertex and the vertex S. This intersection is provided as output for display while the invisible second vertex is saved as the new vertex S.
The algorithm continues from an invisible vertex stored as a vertex S to the next vertex of the polygon. If this vertex is also invisible, no intersection need be computed. The new vertex is simply stored as the new vertex S, and no output is provided for the display. If, on the other hand, the new vertex is visible so that the vertices are on opposite sides of the clipping plane, a new intersection I is computed between the clipping plane of interest and the line joining the new vertex and the present vertex S; this intersection I is provided as an output for the display. The new vertex being visible is also provided as an output for display, and the new vertex becomes the vertex S.
This operation continues until the polygon closes on itself. Closure is detected when it is explicitly requested by the system, i.e. the last vertex is tagged, or a close operation is requested. Once completed with respect to one clipping plane, the operation for the polygon continues for each of the remaining clipping planes. In general, because of the number of individual operations required by the algorithm, this requires that a three dimensional image clipping determination must be handled by six individual clipping engines in order to be completed within a reasonable period.
The operation of the Sutherland-Hodgman clipping algorithm is simple and completely accurate. Moreover, it handles very complicated situations such as those in which all of the vertices of a polygon lie outside but surrounding the visible area. In such a situation, the polygon may influence what appears in the visible area without any of its sides being visible. For example, such a polygon controls the color of the visible area or what appears in the visible area without providing an edge within the visible area.
While the implementations of the Sutherland-Hodgman algorithm provide correct clipping, they require a substantial amount of computer hardware and incur substantial execution costs. For example, in a particular system utilizing the Sutherland-Hodgman algorithm, at least half of the hardware utilized for providing the graphics output system is used for clipping while the necessary use of such hardware is but a trivial part of the operation of the system. Even so, the system is required to process each polygonal form through the clipping algorithm hardware whether or not it would be affected by the clipping operation.
This result occurs in the exemplary system and in most operations because there are a number of situations in which the use of the clipping algorithm is trivial. For example, if all of the vertices of the polygon lie within the visible area, then the polygon may simply be displayed upon the computer output display, and the clipping algorithm need not be utilized. This is a substantial portion of the operation. Moreover, if all of the vertices lie outside of the visible area in an area such that no lines defining the polygon affect the visible area, then the clipping algorithm need not be applied. This also is a substantial portion of the system operation using the Sutherland-Hodgman algorithm.
It is, therefore, an object of the present invention to provide an efficient graphics process for clipping two and three dimensional images.
It is another object of the present invention to speed the clipping process in the presentation of computer graphics.
It is an additional object of the present invention to improve clipping algorithms by eliminating those trivial portions of such algorithms which find substantial use in computer graphics systems.
It is another object of the present invention to reduce the cost of computer graphics hardware.